from operator import itemgetter
from collections import defaultdict


# Input

index = dict()  # Map from IATA to id
n = 0  # Number of ids
iatas, names, coords = [], [], []
with open('airports.txt') as fp:
    ID, NAME, CITY, COUNTRY, IATA, ICAO, LAT, LON = range(8)
    for line in fp.read().split('\n')[:-1]:
        l = line.split(',')
        # Keep only airports with a known IATA code.
        iata, name = l[IATA], l[NAME].replace('\\', '').replace('\'', '')
        if iata:
            index[iata] = n
            iatas.append(iata)
            names.append(name)
            n += 1
            try:
                coords.append((float(l[LAT]), float(l[LON])))
            except:
                coords.append((0, 0))

depart = [0] * n  # Count departures
arrive = [0] * n  # Count arrivals
routes = defaultdict(lambda: defaultdict(int))  # Map <origin, destiny, count>
with open('routes.txt') as fp:
    AIR_CODE, AIR_ID, ORIG_CODE, ORIG_ID, DEST_CODE, DEST_ID = range(6)
    for line in fp.read().split('\n')[:-1]:
        l = line.split(',')
        ocode, dcode = l[ORIG_CODE], l[DEST_CODE]
        # Ignores airports that aren't in aiports.txt.
        if ocode in index and dcode in index:
            orig, dest = index[ocode], index[dcode]
            depart[orig] += 1
            routes[orig][dest] += 1
            arrive[dest] += 1


# Pagerank

pagerank = [1 / n] * n
for i in range(100):
    # print('iteration {:03}, {:.10f}'.format(i, pagerank[0]))
    q = [0] * n
    pool = 0  # Acumulated pagerank of airports without departures.

    for orig in range(n):
        # Split pagerank across destinations.
        if depart[orig] > 0:
            # There are routes from the airport, split proportionally.
            for dest in routes[orig]:
                q[dest] += routes[orig][dest] / depart[orig] * pagerank[orig]
        else:
            # No routes from this airport, split equally among every airport.
            # For efficiency, instead of adding it now, add it's pagerank to a
            # pool that is  distributed at the end of the iteration.
            pool += pagerank[orig]

    # Distribute pool accross all airports.
    for k in range(n):
        q[k] += 1 / n * pool

    # Apply dampening.
    d = .85
    for k in range(n):
        pagerank[k] = q[k] * d + (1 - d) / n

# Results

# Sort results by pagerank
ranking = sorted(zip(range(n), pagerank), key=itemgetter(1), reverse=True)

# Print ranking of results
# print('order pagerank      name')
# for i, (k, pr) in enumerate(ranking[:10]):
#     msg = '[{:04}] {:.10f} {} {}'
#     print(msg.format(i, pr, iatas[k], names[k]))

# Generate code that can be used with sigma.js to display an interactive graph
print("""
<html>
<head>
<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.8.3/jquery.min.js"></script>
<script type="text/javascript" src="http://sigmajs.org/js/sigma.min.js"></script>
<script type="text/javascript">
$(document).ready(function() {
  var sigRoot = document.getElementById('sig');
  var sigInst = sigma.init(sigRoot).drawingProperties({
    defaultLabelColor: '#fff',
    defaultLabelSize: 14,
    defaultLabelBGColor: '#000',
    defaultLabelHoverColor: '#000',
    labelThreshold: 6,
    defaultEdgeType: 'curve'
  }).graphProperties({
    minNodeSize: 0.5,
    maxNodeSize: 10,
    minEdgeSize: 0.25,
    maxEdgeSize: 5
  });

  // Bind events :
  var greyColor = '#333';
  var redColor = '#f50';
  var blueColor = '#0bf';
  sigInst.bind('overnodes',function(event){
      var nodes = event.content;
      var neighbors = {};
      sigInst.iterEdges(function(e){
          if(nodes.indexOf(e.source)<0 && nodes.indexOf(e.target)<0){
              if(!e.attr['grey']){
                  e.attr['true_color'] = e.color;
                  e.color = greyColor;
                  e.attr['grey'] = 1;
              }
          }else if (nodes.indexOf(e.source)<0){
              e.color = e.attr['grey'] ? e.attr['true_color'] : redColor;
              e.attr['grey'] = 1;

              neighbors[e.source] = 1;
              neighbors[e.target] = 1;

          }else{
              e.color = e.attr['grey'] ? e.attr['true_color'] : blueColor;
              e.attr['grey'] = 1;

              neighbors[e.source] = 1;
              neighbors[e.target] = 1;

          }
      }).iterNodes(function(n){
          if(!neighbors[n.id]){
              if(!n.attr['grey']){
                  n.attr['true_color'] = n.color;
                  n.color = greyColor;
                  n.attr['grey'] = 1;
              }
          }else{
              n.color = n.attr['grey'] ? n.attr['true_color'] : n.color;
              n.attr['grey'] = 0;
          }
      }).draw(2,2,2);
  }).bind('outnodes',function(){
      sigInst.iterEdges(function(e){
          e.color = e.attr['grey'] ? e.attr['true_color'] : e.color;
          e.attr['grey'] = 0;
      }).iterNodes(function(n){
          n.color = n.attr['grey'] ? n.attr['true_color'] : n.color;
          n.attr['grey'] = 0;
      }).draw(2,2,2);
  });
(sigInst
""")
nodes = set()
msg = """).addNode('{0}', {{label:'{1} {2:.1f}', size:{2}, x:{3}, y:{4}}}"""
for k, pr in ranking[:20]:
    nodes.add(k)
    x, y = coords[k][1], -coords[k][0]
    print(msg.format(iatas[k], names[k], pr * 1000, x, y))
msg = """).addEdge('{0}-{1}','{0}','{1}', {{ size: {2}}}"""
for orig in routes:
    for dest in routes[orig]:
        if orig in nodes and dest in nodes:
            print(msg.format(iatas[orig], iatas[dest], routes[orig][dest]))
print("""
).draw(); }); </script>
<style type="text/css">/* sigma.js context : */ .sigma {
margin-left:auto;
margin-right:auto;
position: relative;
border-radius: 4px;
-moz-border-radius: 4px;
-webkit-border-radius: 4px;
background: #222;
width: 100%;
height: 100%;
top: 0;
left: 0;
}</style>
</head><body><div class="sigma" id="sig"></div></body></html>
""")
